package algorithm.leetcode.I1to100;

/**
 * 实现字符串表示的两个数字的乘法,返回也是字符串
 * 即大数相乘
 */

public class Q43 {

    public String multiply(String num1, String num2) {
        if (num1.length() == 1 && Integer.parseInt(num1) == 0) return "0";
        if (num2.length() == 1 && Integer.parseInt(num2) == 0) return "0";

        // digit的范围在0到81之间, [0,0,...,0,高位,...,低位]
        int[] digitArray = new int[num1.length() + num2.length()];

        for (int i = 0; i < num1.length(); i++) {
            for (int j = 0; j < num2.length(); j++) {
                // 这一行的索引关系有点难想到
                digitArray[i + j + 1] += (num1.charAt(i)-48) * (num2.charAt(j)-48);
            }
        }

        int carry = 0, digit = 0;
        StringBuilder res = new StringBuilder();
        for (int i = digitArray.length-1; i >= 0; i--) {
            int temp = carry + digitArray[i];
            digit = temp % 10;
            carry = temp / 10;
            res.append(digit);
        }

        return res.reverse().toString().replaceFirst("^0+", "");

    }

    public static void main(String[] args) {
        Q43 q43 = new Q43();
        System.out.println(q43.multiply("123", "456"));
    }

}
